package org.raymond.iworks.study.basic.structure.graph;

/*
为什么要有图
1) 线性表局限于一个直接前驱和一个直接后继的关系
2) 树也只能有一个直接前驱也就是父节点
3) 需要表示多对多的关系时,就用到了图

图是一种数据结构,其中节点可以具有零个或多个相邻元素,两个节点之间的连接称为边.
节点也可以称为顶点.
图的常用概念:
1) 顶点(vertex)
2) 边(edge): 如下图,有A-B,B-C,A-D,B-D,D-E
3) 路径: 比如从D->C的路径有
3.1) D->B->C
3.2) D->A->B->C
4) 无向图: 顶点之间的连接没有方向,比如A-B,即可以是A->B,也可以是B->A

  B
    C
A
     E
  D
5) 有向图: 顶点之间的连接有方向,比如A->B,只能是A->B,不能是B->A
6) 带权图: 边 带权值的图也叫网
北京  1463  上海
2160       700
香港  808  台北

图的表示方式有两种,二维数组表示(邻接矩阵);链表表示(邻接表).
邻接矩阵:
邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵的
row和col表示的是1...n个点
   [0]
[1]   [3]
   [2]
[4]   [5]

0-没有直连,1-直接相连
  0 1 2 3 4 5
0[0 1 1 1 1 0]
1[1 0 0 0 1 0]
2[1 0 0 0 1 1]
3[1 0 0 0 0 1]
4[1 1 1 0 0 1]
5[0 0 1 1 1 0]

邻接表:
1) 邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在的,会
造成空间的一定损失
2) 邻接表的实现只关心存在的边,不关心不存在的边.因此没有空间浪费,邻接表
由数组+链表组成
0 [1]->[2]->[3]->[4]->
1 [0]->[4]->
2 [0]->[4]->[5]->
3 [0]->[5]->
4 [0]->[1]->[2]->[5]->
5 [2]->[3]->[4]->
说明:
1) 标号为0的节点的相关联的节点为1,2,3,4
2) 标号为1的节点的相关联的节点为0和4
3) 标号为2的节点的相关联的节点为0,4,5
4) ...
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 图的创建思路分析
 * 1) 存储顶点String, 用ArrayList
 * 2) 存储邻接矩阵,用二维数组 int[][]
 *
 * 图的深度优先遍历介绍
 * 图遍历介绍
 * 所谓图的遍历,即是对节点的访问.一个图有那么多个节点,如何遍历这些节点,需要特定的
 * 策略.一般有两种访问策略. 深度优先和广度优先
 * 深度优先遍历基本思想
 * 图的深度优先搜索(Depth First Search)(DFS)
 * 1) 深度优先遍历.从初始访问节点出发,初始访问节点可能有多个邻接节点,深度优先遍历的策略
 * 就是首先访问第一个邻接节点,然后再以这个被访问的邻接节点作为初始节点,访问它的第一个邻接
 * 节点,可以这样理解:每次都在访问完当前节点后首先访问当前节点的第一个邻接节点.
 * 2) 我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个节点的所有邻接节点进行
 * 横向访问.
 * 3) 显然,深度优先搜索是一个递归的过程.
 * 深度优先遍历算法步骤
 * 1) 访问初始节点v,并标记点v为已访问
 * 2) 查找节点v的第一个邻接节点w
 * 3) 若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个节点继续.
 * 4) 若w未被访问,对w进行深度优先遍历递归(即把w当作另一个v,然后进行步骤123)
 * 5) 查找节点v的w邻接节点的下一个邻接节点,转到步骤3.
 *
 * 注:在邻接矩阵中,邻接节点即与访问节点相连的其他节点,按邻接矩阵中另一维数组元素的
 * 排列顺序访问.
 * 访问节点与另一维的同节点之间不直连
 *
 * 图的广度优先遍历基本思想
 * 图的广度优先搜素(Broad First Search)
 * 类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的节点的顺序.
 * 以便按这个顺序来访问这些节点的邻接节点.
 *
 * 广度优先算法步骤
 * 1) 访问初始节点v并标记节点v为已访问
 * 2) 节点v入队列
 * 3) 当队列非空时,继续执行,否则v节点的算法结束
 * 4) 出队列,取得队头节点u.
 * 5) 查找节点u的第一个邻接节点w
 * 6) 若节点u的邻接节点w不存在,则转到步骤3；否则循环执行以下三个步骤:
 * 6.1) 若节点w尚未被访问,则访问节点w并标记为已访问
 * 6.2) 节点w入队列
 * 6.3) 查找节点u的继w邻接节点后的下一个邻接节点w,转到步骤6.
 */
/*
深度优先与广度优先的区别:
深度优先是只要遇到有相邻节点就去遍历深挖,暂时放弃当前节点的其他相邻节点
广度优先是优先遍历当前节点的所有相邻节点
 */
public class GraphDemo {

    public static void main(String[] args) {
        test2();
    }

    public static void test1(){
        int n=5;
        String[] vertexValue = {"A","B","C","D","E"};
        var graph = new Graph(n);
        for(String s : vertexValue){
            graph.insertVertex(s);
        }
        /*
        添加边
          B
            E
        C
           D
         A
         */
        //连线关系: A-B,A-C,B-C,B-D,B-E
        graph.insertEdge(0, 1, 1); // A-B
        graph.insertEdge(0, 2, 1); // A-C
        graph.insertEdge(1, 2, 1); // B-C
        graph.insertEdge(1, 3, 1); // B-D
        graph.insertEdge(1, 4, 1); // B-E
        graph.showGraph();

        System.out.println("深度遍历");
        graph.dfs();
        graph.reset();
        System.out.println("广度遍历");
        graph.bfs();
    }

    public static void test2(){
        String[] vertexValue = {"1","2","3","4","5","6","7","8"};
        int n = vertexValue.length;
        var graph = new Graph(n);
        for(String s : vertexValue){
            graph.insertVertex(s);
        }
        /*
            1
         2    3
        4 5  6 7
         8
         */
        graph.insertEdge(0, 1, 1);// 1->2
        graph.insertEdge(0, 2, 1);// 1->3
        graph.insertEdge(1, 3, 1);// 2->4
        graph.insertEdge(1, 4, 1);// 2->5
        graph.insertEdge(3, 7, 1);// 4->8
        graph.insertEdge(4, 7, 1);// 5->8
        graph.insertEdge(2, 5, 1);// 3->6
        graph.insertEdge(2, 6, 1);// 3->7
        graph.insertEdge(5, 6, 1);// 6->7

        // 深度优先遍历顺序 1->2->4->8->5->3->6->7
        System.out.println("深度遍历");
        graph.dfs();
        graph.reset();
        System.out.println("广度遍历");
        // 广度优先遍历顺序 1->2->3->4->5->6->7->8
        graph.bfs();
    }
}

class Graph {
    // 存储图的顶点
    private List<String> vertexes;
    // 存储图的邻接矩阵
    private int[][] edges;
    // 表示边的数目
    private int numOfEdges;
    // 定义数组,记录某个顶点是否被访问过
    private boolean[] isVisited;

    public Graph(int n) {
        this.vertexes = new ArrayList<>(n);
        this.edges = new int[n][n];
        this.numOfEdges = 0;
        this.isVisited = new boolean[n];
    }

    public void reset(){
        isVisited = new boolean[numOfEdges];
    }

    /**
     * 对一个节点进行广度优先遍历的方法
     * 访问节点A,将A加入队列末尾,
     * 队列非空,从队列弹出节点A,
     * 在A行上得到与节点A相邻的第一个邻接节点B,
     * B未被访问过,访问节点B,将B加入队列末尾,
     * B已被访问过,从A行得到节点B之后的第一个与A相邻的节点C,
     * C未被访问过,访问节点C,将C加入队列末尾,
     * C已被访问过,A行上C节点之后没有与A相邻的节点,
     * 队列不为空,从队列末尾弹出节点C,
     * 在C行上得到与节点C相邻的第一个相邻节点A,
     * A已被访问过,从C行得到节点A之后的第一个与C相邻的节点B,
     * B已被访问过,C行上B节点之后没有与C相邻的节点,
     * 队列不为空,从队列末尾弹出节点B,
     * 在B行上得到与节点B相邻的第一个相邻节点A,
     * A已被访问过,从B行得到节点A之后的第一个与B相邻的节点C,
     * C已被访问过,从B行得到节点C之后的第一个与B相邻的节点D,
     * D未被访问过,访问节点D,将D加入队列末尾,
     * D已被访问过,从B行得到节点D之后的第一个与B相邻的节点E,
     * E未被访问过,访问节点E,将E加入队列末尾,
     * E已被访问过,B行上E节点之后没有与B相邻的节点,
     * 队列不为空,从队列末尾弹出节点E,
     * 在E行上得到与节点E相邻的第一个相邻节点B,
     * B已被访问过,E行上B节点之后没有与E相邻的节点,
     * 队列不为空,从队列末尾弹出节点D,
     * 在D行上得到与节点D相邻的第一个相邻节点B,
     * B已被访问过,D行上B节点之后没有与D相邻的节点,
     * 全部节点遍历完毕
     */
    private void bfs(boolean[] isVisited, int i){
        // 表示队列的头节点对应的下标
        int u;
        // 邻接节点w
        int w;
        // 队列,记录节点的访问顺序
        var queue = new LinkedList<Integer>();
        // 访问节点,输出节点信息
        System.out.println(getValueByIndex(i)+"=>");
        // 标记为已访问
        isVisited[i] = true;
        // 将节点加入队列
        queue.addLast(i);
        while(!queue.isEmpty()){
            // 取出队列的头节点下标
            u = queue.removeFirst();
            // 得到第一个邻接点的下标w
            w = firstNeighbor(u);
            // 是否找到第一个邻节点
            while (w!=-1){
                // 是否被访问过
                if(!isVisited[w]){
                    System.out.println(getValueByIndex(w)+"=>");
                    // 标记已访问
                    isVisited[w]=true;
                    // 入队
                    queue.addLast(w);
                }
                // 已访问过,则以u为被访问节点,找w的下一个节点
                w = nextNeighbor(u, w); // 体现出广度优先
            }
        }
    }

    /**
     * 遍历所有的节点,都进行广度优先搜索
     */
    public void bfs(){
        for(int i=0; i<getNumOfVertexes(); i++){
            if(!isVisited[i]){
                bfs(isVisited, i);
            }
        }
    }

    /**
     * 得到第一个邻接节点的下标
     * @param index 被访问节点的下标
     * @return 如果存在,就返回下标,否则返回-1
     */
    public int firstNeighbor(int index){
        for(int j=0; j<vertexes.size(); j++){
            if(edges[index][j]>0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1 被访问节点
     * @param v2 前一个邻接节点
     * @return
     */
    public int nextNeighbor(int v1, int v2){
        // j:从前一个邻接节点开始访问的节点的下标
        for(int j=v2+1; j<vertexes.size(); j++){
            if(edges[v1][j]>0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 深度优先搜索(Deep First Search)
     * 访问节点A,得到第一个与A相接的邻接节点B,
     * B未访问过,递归
     * 访问节点B,得到第一个与B相接的邻接节点A,
     * A已访问过,继续从B行遍历A节点之后的与B相接的节点C,
     * C未访问过,递归
     * 访问节点C,得到第一个与C相接的邻接节点A,
     * A已访问过,继续从C行遍历A节点之后的与C相接的节点B,
     * B已访问过,B节点之后没有与C相接的节点,
     * 继续从B行遍历C节点之后与B相接的节点D,
     * D未访问过,递归
     * 访问节点D,得到第一个与D相接的邻接节点B,
     * B已访问过,B节点之后没有与D相接的节点,
     * 继续从B行遍历D节点之后与B相接的节点E,
     * E未访问过,递归
     * 访问节点E,得到第一个与E相接的邻接节点B,
     * B已访问过,B节点之后没有与E相接的节点,
     * 继续从A行遍历B节点之后与A相接的节点C,
     * C已访问过,C节点之后没有与A相接的节点,
     * 全部节点遍历完毕
     * @param isVisited
     * @param i 被访问节点的下标,第一次访问的节点是0
     */
    private void dfs(boolean[] isVisited, int i){
        // 访问指定节点,并输出
        System.out.println(getValueByIndex(i)+"->");
        // 将节点设置为已访问
        isVisited[i]=true;
        // 查找节点i的第一个邻接节点w
        int w = firstNeighbor(i);
        // 判断是否有邻接节点
        while(w!=-1){
            if(!isVisited[w]){
                dfs(isVisited, w);
            }
            // 如果w已被访问过
            w = nextNeighbor(i, w);
        }
    }
    // 对dfs进行重载,遍历所有的节点,并进行dfs
    // 防止非连通图,连通图不需要
    public void dfs(){
        // 遍历所有的节点,进行dfs回溯
        for(int i=0; i<getNumOfVertexes(); i++){
            if(!isVisited[i]){
                dfs(isVisited, i);
            }
        }
    }

    // 返回节点的个数
    public int getNumOfVertexes(){
        return vertexes.size();
    }
    // 返回边的个数
    public int getNumOfEdges(){
        return numOfEdges;
    }
    // 返回指定节点的数据
    public String getValueByIndex(int i){
        return vertexes.get(i);
    }
    // 返回v1和v2的权值
    public int getWeight(int v1, int v2){
        return edges[v1][v2];
    }
    // 显示图对应的矩阵
    public void showGraph(){
        for(int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }
    // 插入顶点
    public void insertVertex(String vertex){
        vertexes.add(vertex);
    }
    /**
     * 添加边,同时也在填充邻接矩阵
     * @param v1 表示第一个顶点的下标
     * @param v2 表示第二个顶点的下标
     * @param weight 两个顶点是否直连,0-未直连,1-已直连
     */
    public void insertEdge(int v1, int v2, int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}